﻿//https://leetcode.cn/problems/distant-barcodes/

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes)
    {
        unordered_map<int, int> hash;
        int maxval = 0, maxcount = 0;
        for (auto x : barcodes)
        {
            if (maxcount < ++hash[x])
            {
                maxcount = hash[x];
                maxval = x;
            }
        }

        int n = barcodes.size();
        vector<int> ret(n);
        //先摆放出现次数最多的数字
        int index = 0;
        for (int i = 0; i < maxcount; i++)
        {
            ret[index] = maxval;
            index += 2;
        }

        //拜访剩余的数字
        hash.erase(maxval);
        for (auto& [x, y] : hash)
        {
            for (int i = 0; i < y; i++)
            {
                if (index >= n) index = 1;
                ret[index] = x;
                index += 2;
            }
        }

        return ret;

    }
};